package 开始的算法算法入门8月.双指针;
// https://leetcode-cn.com/problems/middle-of-the-linked-list/
public class 链表的中间结点0816 {


      public class ListNode {
          int val;
          ListNode next;
          ListNode() {}
          ListNode(int val) { this.val = val; }
          ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      }

    class Solution {
        public ListNode middleNode(ListNode head) {
            ListNode[] A = new ListNode[100];
            int t = 0;
            while (head != null) {
                A[t++] = head;
                head = head.next;
            }
            return A[t / 2];
        }
    }
    class Solution1 {
        public ListNode middleNode(ListNode head) {
            int n = 0;
            ListNode cur = head;
            while (cur != null) {
                ++n;
                cur = cur.next;
            }
            int k = 0;
            cur = head;
            while (k < n / 2) {
                ++k;
                cur = cur.next;
            }
            return cur;
        }
    }
    class Solution2 {
        public ListNode middleNode(ListNode head) {
            ListNode slow = head, fast = head;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }
    }

}
